//026. 倒数周期
//        一个单位分数就是分子为 1 的分数，分子从 2 到 10 的单位分数的小数表示分别如下：
//        1/2 = 0.5
//        1/3 = 0.(3)
//        1/4 = 0.25
//        1/5 = 0.2
//        1/6 = 0.1(6)
//        1/7 = 0.(142857)
//        1/8 = 0.125
//        1/9 = 0.(1)
//        1/10 = 0.1
//        其中 0.1(6)的意思是 0.166666⋯，它的循环节长度是一位， 1/7 的循环节长度是六位。
//        对于 d<1000，求使得 1/d 包含的循环节长度最长的 d 的值。
//        答案：983

import java.util.HashMap;
import java.util.Map;

//获得称号："遇数学则寄"
//模拟小学列竖式除法
//不够除则补0
//由于除数不变，如果余数以前出现过，则说明进入循环
public class Week026 {
    static final int NUM = 1000;

    static int getCycleLength(int divisor) {
        int res = 1;
        Map<Integer, Integer> map = new HashMap<>();
        for (int cur = 0; true; ++cur) {
            if (map.containsKey(res)) {
                return cur - map.get(res);
            }
            map.put(res, cur);
            res = res * 10 % divisor;
            //能整除
            if (res == 0) {
                return 0;
            }
        }
    }

    static void run() {
        int ansValue = 3, ansLength = 1;
        for (int i = 6; i < NUM; ++i) {
            int length = getCycleLength(i);
            if (length > ansLength) {
                ansValue = i;
                ansLength = length;
            }
        }
        System.out.println(ansValue);
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        run();
        System.out.println("\n程序运行时间：" + (System.nanoTime() - startTime) + "ns.");
    }
}
